package leecode

import "math"

func maxSumSubmatrix(matrix [][]int, target int) int {
	result := math.MinInt64
	for k := 0; k < len(matrix); k++ {
		mergeRow := make([]int, len(matrix[k])) //每一行的元素
		for i := k; i < len(matrix); i++ {
			for j := 0; j < len(matrix[i]); j++ {
				mergeRow[j] += matrix[i][j]
			}
			//不超过K的最大连续子数组
			for x := 0; x < len(matrix[i]); x++ {
				temp := 0
				for y := x; y < len(matrix[i]); y++ {
					temp += mergeRow[y]
					if temp == target {
						return target
					} else if temp < target {
						result = max(result, temp)
					}
				}
			}
		}
	}
	return result
}
